Heuristics그리디 알고리즘도 일종의 휴리스틱 알고리즘이다.
휴리스틱 알고리즘은 항상 최적해를 찾지 못하지만, 최적해를 보장할 수 있는 문제들이 존재하며
이는 높은 성능으로 연산을 처리할 수 있다.
(활동 선택 문제에서 그리디 알고리즘을 통해 얻은 해가 최적임을 보장한다.)
그리디 알고리즘 문제로의 변환
1. 하나의 선택을 하면 풀어야 할 부분 문제도 하나만 남도록 최적화 문제로 바꿈
2. 그리디 선택을 하는 것이 언제나 안전하도록 원래 문제의 최적해들 중에서 그리디 선택을 하는 것이 반드시 존재함을 증명
3. 그리디 선택을 했을 때, 그리디 선택과 남아 있는 부분 문제에 대한 최적해와 결합하면 원래 문제에 대한 최적해를 얻을 수 있음을
증명한다.(최적 부분 구조)
- 그리디 선택 특성: 전체적인 최적해는 부분적인 최적 선택을 함으로서 만들 수 있다.
-> 매 단계 그리디 선택이 전역적(globally) 최적해를 만들어 냄을 증명해야 함
(부분 문제에 대한 전역적인 최적해를 검사)
- 최적 부분 구조: 문제에 대한 최적해가 그 문제의 부분 문제에 대한 최적해를 포함한다.
최적 부분 구조는 Dynamic Programming과 Greedy Algorithm을 이용하기 위한 조건
0-1 배낭 문제(0-1 Knapsack Problem) & 분할 가능 배낭 문제(Fractional knapsack Problem)둘 다 최적 부분 구조 특성을 가지기에 동적 프로그래밍을 이용 가능하다.
물건 j를 선택했을 때 최적인 경우, j를 제외한 n-1개의 물건 중 W-w_j의 파운드를 넘지 않는 문제로 바뀜
분할 가능 배낭 문제는 파운드당 가격 v_i/w_i가 높은 순으로 가방을 채울 때 최대 이득을 얻을 수 있음을 명확하기 때문에
그리디 알고리즘을 이용할 수 있다. 하지만, 0-1배낭 문제는 그리디 알고리즘을 해결이 불가능하다.